package map;

import java.util.*;

public class LongestWordInDictionaryThroughDeleting524 {
    public String findLongestWord(String s, List<String> dictionary) {
        //预处理
        Map<Character, TreeSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            TreeSet<Integer> list = map.getOrDefault(s.charAt(i), new TreeSet<>());
            list.add(i);
            map.put(s.charAt(i), list);
        }

        String result = "";
        for (int i = 0; i < dictionary.size(); i++) {
            String dic = dictionary.get(i);
            if (judge(dic, map)) {
                if (dic.length() > result.length()) {
                    result = dic;
                } else if (dic.length() == result.length() && compare(result,dic)) {
                    result = dic;
                }
            }

        }
        return result;
    }
    public boolean compare(String a,String b){
        for (int i = 0; i < a.length(); i++) {
            if(a.charAt(i)>b.charAt(i)){
                return true;
            }
            if(a.charAt(i)<b.charAt(i)){
                return false;
            }
        }
        return false;
    }
    public boolean judge(String s, Map<Character, TreeSet<Integer>> map) {
        int index = -1;
        for (int j = 0; j < s.length(); j++) {
            TreeSet<Integer> treeSet = map.get(s.charAt(j));
            if (treeSet == null || treeSet.size() == 0) {
                return false;
            }
            Integer ceiling = treeSet.ceiling(index+1);
            if (ceiling == null) {
                return false;
            }

            index = ceiling;
        }
        return true;
    }
}
